Tra Bui's First Web Page

Welcome Homepage

Hello! I'm Tra Bui and this is my first website!

Linkedin | Email | Facebook | Github | Leetcode | My CV

THEORETICAL COMPUTATION QUESTIONS (PROFESSOR CHRISTOS)

1. What is a decision problem?

- In computational theory, a decision problem is a problem that can be answered with “yes” or “no” depending on the sets of input. One example of a decision problem would be “Is X a prime number, given x is nonnegative?”

2. What does it mean for a decision problem to be decidable?

- A decision problem is recognized as “decidable” when there are some possible algorithms that can determine the answer to that decision. On the other hand, for “undecidable” decision problems, there exists proof to show that it is impossible to construct an algorithm to categorize the answer into “yes” or “no”.

3. What is the class P? What is the class NP?

- For a decidable problem, the algorithm’s execution time will depend on the size of inputs that it has to work with. For example, back to the “Is X a prime number “ question, the larger X is, the more time it will take for the algorithm to run and determine the answer. With this idea, scientists come up with a unit called “n” which is used to calculate the size of the inputs.

- Computer scientists use the notation “Big O” to talk about the time complexity (the amount of time to execute an algorithm) or space complexity (memory size needed for the inputs).

- A problem will belong to class P if we can construct algorithms that solve it in polynomial time (P stands for “polynomial), or in computational language, O(nc) time with c is an independent constant.

- A problem is in class NP if it is easier to verify its solution rather than construct a direct algorithm to solve it (NP stands for “non-deterministic polynomial”).

4. What is the intuitive meaning of the “P versus NP” question?

- The “P versus NP” question presents an inquiry asking whether problems whose solutions can be verified (check the validity of the answer) in polynomial time can also be solved in polynomial time.

5. If you resolve the P versus NP question, how much richer will you be?

- The P versus NP problem is one of the “Millenium Prize Problems”, which remains unsolved until now. If you solve this problem, you will get 1 million $ prize.


Reference and websites for more information

Explained P vs. NP: https://news.mit.edu/2009/explainer-pnp
Millenium Prize Problem: https://www.businessinsider.com/p-vs-np-millennium-prize-problems-2014-9
P vs. NP and the Computational Complexity Zoo: https://www.youtube.com/watch?v=YX40hbAHx3s
Introduction to Big O Notation and Time Complexity: https://www.youtube.com/watch?v=D6xkbGLQesk